import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网:BM54 三数之和
 * <a href="https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=295&tqId=731&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Data: 2023-04-12
 * Time: 21:33
 */

/**
 * 主要思路：
 * 找到 a+b+c = 0 即找到 b+c = -a ，同时根据题目中的条件三元组（a、b、c）中的元素必须按非降序排列，
 * 因此我们需要先把数组进行升序排序，在针对每一个不同的 a ，利用前后指针的方法遍历数组中存在的 b+c = -a
 * 的二元组（b，c），同时根据题目中的不能包含重复的三元组，因此我们需要对 a，b，c 操作的时候均需要去重。
 * 前后指针法：即针对有序数组，一个指针 left 从数组最前面开始，一个指针 right 在数组最后面开始，
 * 若num[left] + num[right] > -a ,则对 right--
 * 若num[left] + num[right] < -a ,则对 left++
 * 直到 left == right 遍历结束
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //判断特殊情况
        if (num == null || num.length <= 2) {
            return res;
        }
        //先升序排序
        Arrays.sort(num);
        //针对每个不同的数 num[i] 寻找三元组
        //因为 a <= b <= c 因此 a 最大为 num 数组的倒数第三个元素
        for (int i = 0; i < num.length-2; i++) {
            //针对 a 去重
            if (i != 0 && num[i-1] == num[i]) {
                continue;
            }
            int target = -1*num[i];
            int left = i + 1;
            int right = num.length-1;
            while (left < right) {
                if (num[left] + num[right] == target) {
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    res.add(temp);
                    //对 b 进行去重
                    while (left < right-1 && num[left] == num[left+1]) {
                        left++;
                    }
                    //对 c 进行去重
                    while (right > left+1 && num[right] == num[right-1]) {
                        right--;
                    }
                    //向中间收缩
                    left++;
                    right--;
                } else if (num[left] + num[right] > target) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return res;
    }
}